﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
////题目1：对数组执行操作
////一个数组如果nums[i] = nums[i+1]
////那就将nums[i]变为原来的2倍并将nums[i+1]变为0
////最后将所有的0放到数组最后将非0放到数组前面，并且不能改变非0数的顺序
////思路：模拟
////方法一：循环一遍将数组进行操作，然后将所有非0的数放到我们开辟的数组里面，最后补齐后面的0
//int* applyOperations(int* nums, int numsSize, int* returnSize)
//{
//	int* ret = (int*)malloc(sizeof(int) * numsSize);
//	if (ret == NULL)
//	{
//		perror("malloc fail");
//		return NULL;
//	}
//	for (int i = 0; i < numsSize - 1; i++)
//	{
//		if (nums[i] == nums[i + 1])
//		{
//			nums[i] = 2 * nums[i];
//			nums[i + 1] = 0;
//		}//先将数组修改为目标数组
//	}
//	int j = 0;
//	//下面开始给ret赋值（非0）
//	for (int i = 0; i < numsSize; i++)
//	{
//		if (nums[i])
//		{
//			ret[j++] = nums[i];
//		}
//	}
//	//（赋值0）
//	for (int i = j; i < numsSize; i++)
//	{
//		nums[i] = 0;//
//	}
//	return nums;
//}
////思路二：直接在原数组上进行操作
//int* applyOperations(int* nums, int numsSize, int* returnSize)
//{
//	int j = 0;//作为非0数的下标
//	for (int i = 0; i < numsSize - 1; i++)
//	{
//		if (nums[i] == nums[i + 1])
//		{
//			nums[i] = 2 * nums[i];
//			nums[i + 1] = 0;
//		}//先修改为目标数组
//	}
//	for (int i = 0; i < numsSize; i++)
//	{
//		if (nums[i])
//		{
//			int val = nums[j];
//			nums[j++] = nums[i];
//			nums[i] = val;
//		}
//	}
//	return nums;
//}
//今日题目：老鼠和奶酪
//有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。
//下标为 i 处的奶酪被吃掉的得分为：
//如果第一只老鼠吃掉，则得分为 reward1[i] 。
//如果第二只老鼠吃掉，则得分为 reward2[i] 。
//给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个非负整数 k 。
//请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大 得分为多少。
int compare(const void* p1, const void* p2)
{
	return ((int*)p2)[2] - ((int*)p1)[2];
}
int miceAndCheese(int* reward1, int reward1Size, int* reward2, int reward2Size, int k)
{
	//思路新创建一个二维数组二维数组的行号代表第几块奶酪，
	//第一列代表被老鼠1吃掉得到的分
	//第二列代表被老鼠2吃掉得到的分
	//第三列代表老鼠1减去老鼠二的分
	int** arr = (int**)malloc(sizeof(int*) * reward1Size);
	if (arr == NULL)
	{
		perror("创建数组失败:");
		return 0;
	}
	for (int i = 0; i < reward1Size; i++)
	{
		int* arr[i] = (int*)malloc(sizeof(int) * 3);
		arr[i][0] = reward1[i];//第一列储存第1只老鼠的分
		arr[i][1] = reward2[i];//第二列储第2只老鼠的分
		arr[i][2] = reward1[i] - reward2[i];//储存两者的差值分
	}
	qsort(arr, reward1Size, sizeof(arr[0]), compare);//依据第三列的分数将二维数组的行号重新排列(有大到小)
	int ans = 0;
	for (int i = 0; i < k; i++)
	{
		ans += arr[i][1];//前k块奶酪交给老鼠1去吃，因为老鼠1得到的分多
	}
	for (int i = k; k < reward1Size; i++)
	{
		ans += arr[i][2];//其余的奶酪交给老鼠二去吃，分数最大
	}
	return ans;
}